package leetcode.code1969;

import leetcode.helper.H;

public class Solution {

	int mod = (int) 1e9 + 7;

	public int minNonZeroProduct(int p) {
		long n1 = f(2, p) - 1;
		long n2 = f(f(2, p) - 2, (1L << (p - 1)) - 1);
		return (int) (n1 * n2 % mod);
	}

	public int minNonZeroProduct2(int p) {
		long n1 = f(2, p) - 1;
		long n2 = f(f(2, p) - 2, f(2, p - 1) - 1);
		return (int) (n1 * n2 % mod);
	}

	private long f(long b, long k) {
		if (k == 0) {
			return 1;
		}
		if (k == 1) {
			return b;
		}
		long ans = f(b, k >> 1);
		ans = ans * ans % mod;
		if ((k & 1) == 0) {
			return ans;
		}
		return ans * b % mod;
	}

	public int minNonZeroProduct4(int p) {
		long n = (1L << (p - 1)) - 1;
		long num = (1L << p) - 1;
		long res = f(num - 1, n) % mod;
		return (int) ((res * (num % mod)) % mod);
	}

//	public int minNonZeroProduct(int p) {
//		return (int) ((((f(2, p) - 1) % mod) * (f(f(2, p) - 2, f(2, p - 1) - 1) % mod)) % mod);
//	}

	private long multiply(long base, long k) {
		long res = 1;
		while (k != 0) {
			if (k % 2 == 1) {
				res = ((res % mod) * (base % mod)) % mod;
			}
			base = ((base % mod) * (base % mod)) % mod;
			k /= 2;
		}
		return res;
	}

	public int minNonZeroProduct3(int p) {
		long n = (1L << (p - 1)) - 1;
		long num = (1L << p) - 1;
		long res = multiply(num - 1, n) % mod;
		return (int) ((res * (num % mod)) % mod);
	}

	private void print(long... a) {
		for (long n : a) {
			System.out.print(n + " ");
		}
		System.out.println("");
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		H.compare(554966674, so.minNonZeroProduct(40));
		H.compare(554966674, so.minNonZeroProduct2(40));
		H.compare(554966674, so.minNonZeroProduct3(40));
//		long mod = (long) 1e9 + 7;
//		System.out.println((1l * 1048576 * 1048576) % mod);
	}

}
